Matematica Discreta: Fondamenti delle Strutture ad Albero

Nel campo della teoria dei grafi, un albero è la personificazione architettonica dell'ordine. A differenza delle reti caotiche in cui potrebbero esistere più percorsi che portano allo stesso punto, un albero fornisce un percorso unico e singolo tra due qualsiasi punti. Questo vincolo strutturale non è una limitazione, ma la base stessa dei sistemi gerarchici – dagli alberi genealogici degli dèi greci alle strutture di directory dei moderni sistemi operativi.

1. L'anatomia di un albero

Prima che esista una gerarchia, abbiamo il Albero libero. La sua definizione è elegante nella sua semplicità:

Definizione 9.1.1

Un (albero libero) $T$ è un grafo semplice in cui per ogni coppia di vertici $v$ e $w$, esiste un percorso semplice unico da $v$ a $w$. Ciò implica che il grafo è sia connesso e aciclico (senza cicli).

Quando identifichiamo un vertice specifico come "origine", creiamo un albero radicato. Questa trasformazione introduce un orientamento spaziale, dove le relazioni sono definite in base alla distanza e alla direzione rispetto alla radice.

Il lessico gerarchico

In un albero con radice $v_0$, considera un percorso semplice $(v_0, v_1, \dots, v_n)$:

Genitore: Il vertice $v_{n-1}$ è il genitore di $v_n$.
Figlio: $v_n$ è un figlio di $v_{n-1}$.
Fratelli: Vertici che condividono lo stesso genitore.
Antenati: Tutti i vertici sul percorso dalla radice a $v_n$ (escludendo $v_n$ stesso in alcuni contesti).
Discendenti: Tutti i vertici che hanno $v$ come antenato.

Metriche strutturali

Livello: La lunghezza del percorso unico dalla radice a un vertice. La radice stessa si trova al Livello 0.
Altezza: Il numero massimo di livello presente nell'albero.
Foglia (vertice terminale): Un vertice senza figli – l'estremità di un ramo.
Vertice interno (ramo): Un vertice che ha almeno un figlio.

🎯 Concetto chiave: Sottoalberi

Un sottoalbero è un sottoinsieme di un albero composto da un vertice e tutti i suoi discendenti. In un sistema di file, questo corrisponde a una cartella e a tutti i file/sottocartelle al suo interno. Nella Figura 9.2.1, la discendenza di Crono (Zeus, Poseidone, Ade, Ares) è un sottoalbero di Urano.

2. Applicazioni nel mondo reale

Gli alberi non sono solo astrazioni matematiche. Sono la colonna portante dell'organizzazione:

Sistemi di file informatici: Il disco 'C:' è la radice; le cartelle sono vertici interni; i file sono foglie.
Organigrammi amministrativi: Il CEO è la radice; i manager sono nodi interni; i collaboratori individuali sono foglie.
Framework decisionali: Risolvere enigmi come Instant Insanity o analizzare la planarità dell'n-cubo spesso richiede la navigazione di spazi di stato simili ad alberi.

DOMANDA 1

Nel contesto dell'Albero Genealogico della Mitologia Greca (Figura 9.2.1), se i figli di Crono sono Zeus, Poseidone, Ade ed Ares, chi sono i fratelli di Ares?

Zeus, Poseidone ed Ade

Urano e Crono

Solo Zeus

Crono e Afrodite

DOMANDA 2

Qual è il livello della radice in qualsiasi albero radicato?

Livello 0

Livello 1

Livello n-1

Dipende dall'altezza

DOMANDA 3

Come si distingue una 'foglia' (vertice terminale) da un 'interno' (vertice ramo)?

Una foglia non ha figli, mentre un vertice interno ne ha almeno uno.

Una foglia si trova sempre al Livello 0.

I vertici interni si trovano sempre all'altezza massima.

Le foglie devono avere fratelli.

DOMANDA 4

Spiega perché, se consentiamo cicli di lunghezza 0 (un percorso da un vertice a sé stesso senza spigoli), un grafo con un solo vertice non è aciclico.

Perché il singolo vertice contenerebbe tecnicamente un ciclo di lunghezza 0.

Perché un albero deve avere almeno due vertici.

Perché un singolo vertice non è connesso.

Perché violerebbe la regola degli n-1 spigoli.

DOMANDA 5

In base al contesto letto, chi è il genitore di Poseidone nell'albero della mitologia greca?

Crono

Urano

Zeus

Afrodite

Lezione 9 Sfida: Logica Strutturale e di Ottimizzazione

Applicazione della Teoria degli Alberi ai Problemi Combinatori

Gli alberi costituiscono la base per risolvere problemi di ottimizzazione e ricerca. Usa i principi degli algoritmi golosi, del backtracking e delle proprietà strutturali per risolvere le seguenti sfide.

In un grafo in cui i vertici rappresentano città e gli spigoli pesati rappresentano i costi di costruzione (a-g, pesi da 5 a 30), come troviamo il sistema stradale meno costoso?

Soluzione: Costruisci un Albero Ricoprente Minimo (MST) utilizzando l'Algoritmo di Prim. Inizia con una qualsiasi città, quindi aggiungi ripetutamente lo spigolo di peso più basso che collega una città del nostro insieme a una fuori dall'insieme, garantendo che non si formino cicli fino a quando tutte le città non siano connesse.

Dimostra che non esiste soluzione al problema delle due regine o del problema delle tre regine.

Soluzione: Per il problema delle due regine (griglia 2x2): Se posizioni una regina in (1,1), attacca il resto della riga, della colonna e della diagonale, lasciando nessun posto sicuro per la seconda regina. Per il problema delle tre regine (griglia 3x3): Posizionare una regina in qualunque cella attacca abbastanza della griglia che le due regine rimanenti non possono essere posizionate senza attaccarsi reciprocamente o la prima regina. Ad esempio, posizionare la prima in (1,1) attacca (1,2), (1,3), (2,1), (3,1), e (2,2), (3,3). Nessuna configurazione di 3 regine evita tutti i conflitti.

Dimostra che se i valori sono 1, 8 e 10 centesimi, un algoritmo goloso non produce sempre il numero minimo di francobolli per una data somma.

Soluzione: Supponiamo di aver bisogno di 16 centesimi di affrancatura. Approccio goloso: Prende il valore più alto possibile (10), poi 1, 1, 1, 1, 1, 1. Totale = 7 francobolli. Approccio ottimale: Prende due francobolli da 8 centesimi. Totale = 2 francobolli. Pertanto, la scelta golosa di 'il più grande per primo' fallisce nel trovare il minimo globale.

Fornisci un algoritmo per costruire un albero binario di ricerca.

Algoritmo: 1. Inizia con il primo elemento come radice. 2. Per ogni elemento successivo $x$: a. Confronta $x$ con il nodo corrente $v$. b. Se $x < v$, muoviti al figlio sinistro. c. Se $x > v$, muoviti al figlio destro. d. Se il figlio obiettivo è nullo, inserisci $x$ lì; altrimenti, ripeti il passo 2 partendo da quel figlio.

Che cosa significa che due alberi liberi sono isomorfi?

Soluzione: Due alberi liberi $T_1$ e $T_2$ sono isomorfi se esiste una biiezione $f: V(T_1) \to V(T_2)$ che preserva l'adiacenza. Cioè, per ogni vertice $v, w$ in $T_1$, esiste uno spigolo tra $v$ e $w$ se e solo se esiste uno spigolo tra $f(v)$ e $f(w)$ in $T_2$. Le proprietà strutturali come i gradi e le lunghezze dei percorsi sono identiche.